def minPathSUm(grid):
    m = len(grid)
    n = len(grid[0])

    def dp(grid,i,j):
        if i==0 and j ==0:
            return grid[0][0]
        if i <0 or j < 0:
            return float("inf")
        return min(dp(grid,i-1,j),
                   dp(grid,i,j-1),
                   )+grid[i][j]
    return dp(grid,m-1,n-1)

def minPathSum2(grid):
    m = len(grid)
    n = len(grid[0])
    memo=[[-1]*n for _ in range(m)]
    def dp(grid,i,j):
        if i == 0 and j == 0:
            return grid[0][0]
        if i < 0 or j < 0:
            return float("inf")

        if memo[i][j] !=-1:
            return memo[i][j]

        memo[i][j]=min(dp(grid,i-1,j),
                   dp(grid,i,j-1),
                   )+grid[i][j]
        return memo[i][j]

    return dp(grid,m-1,n-1)


if __name__=="__main__":
    grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
    r =minPathSum2 (grid)
    print(r)